package bintree.leetcode;

//110. 平衡二叉树

import java.util.HashMap;
import java.util.Map;

public class Num110_isBalanced {
    //方法1：
//    public boolean isBalanced(TreeNode root) {
//        if(root==null){
//            return true;
//        }
//        int left=maxDepth(root.left);
//        int right=maxDepth(root.right);
//        if(Math.abs(left-right)>1){
//            return false;
//        }
//        return isBalanced(root.left) && isBalanced(root.right);
//    }

    //2.减少重复
    private Map<TreeNode,Integer> map=new HashMap<>();
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        int left=0;
        int right=0;

        if(map.containsKey(root.left)){
            // 此时左树的高度已经被计算过了，直接从map中取出节点值对于的高度
            left=map.get(root.left);
        }else {
            left=maxDepth(root.left);
            // 将该节点和对于的高度存入Map中
            map.put(root.left,left);
        }

        if(map.containsKey(root.right)){
            right=map.get(root.right);
        }else {
            right=maxDepth(root.right);
            map.put(root.right,right);
        }
        int abs=Math.abs(left-right);
        if(abs>1){
            return false;
        }
        // 继续递归判断左树要满足平衡 并且 右树也要满足平衡
        return isBalanced(root.left) && isBalanced(root.right);
    }


    //104. 二叉树的最大深度
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        //简写
        return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
    }
}
